不懂回文自动机的点这里
如果单纯的记录每个点结束回文串的数量，因为我们用的增量法 ， 只会被计算一次 ， 第二个样例都过不了。
所以在构建回文自动机后 ， 我们将每一个 , 就可以避免由上述方法带来的影响了。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Mod 51123987
const int MAXN = 300000 , MAXK = 26;
char str[ MAXN + 5 ];
struct Palindromes_Automaton {
int Size , Last , Root0 , Root1 , Trans[ MAXN + 5 ][ MAXK + 5 ] , Link[ MAXN + 5 ];
int Len[ MAXN + 5 ] , Cnt[ MAXN + 5 ];
Palindromes_Automaton( ) {
Root0 = Size ++ , Root1 = Size ++; Last = Root1;
Len[ Root0 ] = 0 , Link[ Root0 ] = Root1;
Len[ Root1 ] = -1 , Link[ Root1 ] = Root1;
}
void Extend( int ch , int dex ) {
int u = Last;
for( ; str[ dex ] != str[ dex - Len[ u ] - 1 ] ; u = Link[ u ] );
if( !Trans[ u ][ ch ] ) {
int Newnode = ++ Size , v = Link[ u ];
Len[ Newnode ] = Len[ u ] + 2;
for( ; str[ dex ] != str[ dex - Len[ v ] - 1 ] ; v = Link[ v ] );
Link[ Newnode ] = Trans[ v ][ ch ]; Trans[ u ][ ch ] = Newnode;
}
Last = Trans[ u ][ ch ];
Cnt[ Last ] ++;
}
void Build( char *str ) {
int len = strlen( str );
for( int i = 0 ; i < len ; i ++ )
Extend( str[ i ] - 'a' + 1 , i );
}
long long Calc( ) {
long long Ans = 0;
for( int i = Size ; i >= 0 ; i -- )
Cnt[ Link[ i ] ] += Cnt[ i ] , Ans = max( Ans , 1ll * Cnt[ i ] * Len[ i ] );
return Ans;
}
}PAM;
int main() {
scanf("%s", str );
PAM.Build( str );
printf("%lld", PAM.Calc( ) );
return 0;
}
